package org.example.everyday;

public class GetMaximumGold {
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    int m,n;
    int[][] grid;
    int ans = 0;

    public static void main(String[] args) {

    }

    /**
     * 输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
     * 输出：24
     * 解释：
     * [[0,6,0],
     *  [5,8,7],
     *  [0,9,0]]
     * 一种收集最多黄金的路线是：9 -> 8 -> 7。
     * @param _grid
     * @return
     */
    public int getMaximumGold(int[][] _grid) {
        grid = _grid;
        int m = grid.length,n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]!=0){
                    dfs(i,j,grid[i][j]);
                }
            }
        }
        return ans;
    }

    private void  dfs(int x, int y, int gold) {
        gold += grid[x][y];
        ans = Math.max(ans,gold);

        int rec = grid[x][y];
        //就表示已经开采过了
        grid[x][y] = 0;
        for (int i = 0; i < dirs.length ; i++) {
            int nx = x+dirs[i][0],ny = y + dirs[i][1];
            if(nx>=0 && nx<m && ny>=0 && ny<n && grid[ny][ny]>0){
                dfs(nx,ny,gold);
            }
        }
        //开采资源还原
        grid[x][y] = rec;
    }
}
